//编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。 
//
// 示例1: 
//
// 
// 输入：[1, 2, 3, 3, 2, 1]
// 输出：[1, 2, 3]
// 
//
// 示例2: 
//
// 
// 输入：[1, 1, 1, 1, 2]
// 输出：[1, 2]
// 
//
// 提示： 
//
// 
// 链表长度在[0, 20000]范围内。 
// 链表元素在[0, 20000]范围内。 
// 
//
// 进阶： 
//
// 如果不得使用临时缓冲区，该怎么解决？ 
//
// Related Topics 哈希表 链表 双指针 👍 172 👎 0

package leetcode.editor.cn;
//leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    /**
     * 位运算超过32位就不行了，当value=33时，左移33等于左移1
     * @param head
     * @return
     */
    public ListNode removeDuplicateNodes(ListNode head) {
        int sumFlag = 0;
        ListNode dummy = head;
        ListNode pre = head;
        while (dummy != null) {
            int value = dummy.val;
            int temp = 1;
            temp <<= (value-1);
            if ((sumFlag & temp) == 0) { // 无重复
                sumFlag |= temp;
                pre = dummy;
            } else {
                pre.next = dummy.next;
            }
            dummy = dummy.next;
        }
        return head;
    }

    public static void main(String[] args) {
        ListNode listNode = ListNodeUtil.initList(16, 33, 26, 29, 36, 26, 25, 30, 5, 25, 7, 23, 3, 1);
        ListNode listNode1 = new Solution().removeDuplicateNodes(listNode);

    }
}
//leetcode submit region end(Prohibit modification and deletion)
